In conventional relational database tables, rows are inserted into a table without regard to any type of ordering. Consequently, when a user submits a query that selects data from the table based on a particular value or range of values, the entire table has to be scanned to ensure that all rows that satisfy the criteria are identified.
Partitioning is a technique that, in certain situations, avoids the need to search an entire table (or other database object). With partitioning, an object, such as a database table, is divided up into sub-tables, referred to as “partitions”. The most common form of partitioning is referred to as range partitioning. With range partitioning, each individual partition corresponds to a particular range of values for one or more columns of the table.
Typically, the criteria used to partition a database object is specified in the statement that creates the database object. For example, the following Structured Query Language (SQL) statement creates a table “sales” that is range partitioned based on date values contained in a column named “saledate”:
create table sales(saledate DATE,productid NUMBER, . . .)partition by range (saledate)partition sal94Q1 values less than to_date (yy-mm-dd,‘94-04-01’)partition sal94Q2 values less than to_date (yy-mm-dd,‘94-07-01’)partition sal94Q3 values less than to_date (yy-mm-dd,‘94-10-01’)partition sal94Q4 values less than to_date (yy-mm-dd,‘95-01-01’)
Execution of this statement creates a table named “sales” that includes four partitions: sal94Q1, sal94Q2, sal94Q3, and sal94Q4. Each partition has “bounds” that dictate which rows are stored in the partition. The bounds of a partition typically correspond to a range of partition key values.
For example, in the “sales” table defined above, the partition key is saledate, and the partition named sal94Q1 includes all rows that have a date less than 94-04-01 in their saledate column. Similarly, the partition named sal94Q2 includes all rows that have a date greater than or equal to 94-04-01 but less than 94-07-01 in their saledate column. The partition named sal94Q3 includes all rows that have a date greater than or equal to 94-07-01 but less than 94-10-01 in their saledate column. The partition named sal94Q4 includes all rows that have a date greater than or equal to 94-10-01 but less than 95-01-01 in their saledate column.
When a database server receives a request to perform an operation, the database server makes a plan of how to execute the query. If the operation involves accessing a partitioned object, part of making the plan involves determining which partitions of the partitioned object, if any, can be excluded from the plan (i.e. which partitions need not be accessed to execute the query). The process of excluding partitions from consideration during the execution of a query that accesses a partitioned object is referred to as “partition pruning”.
Unfortunately, conventional pruning techniques can only be applied to a limited set of statements. For example, the database server can perform partition pruning when the statement received by the database server explicitly limits itself to a partition or set of partitions. Thus, the database server can exclude from the execution plan of the statement “select*from sales PARTITION(sal94Q1)” all partitions of the sales table other than the sal94Q1 partition.
The database server can also perform partition pruning on statements that do not explicitly limit themselves to particular partitions, but which select data based on the same criteria that was used to partition the partitioned object. For example, the statement:                select*from sales where saledate between (94-04-01) and (94-06-15)        
does not explicitly limit itself to particular partitions. However, because the statement limits itself based on the same key (saledate) that was used to partition the sales table, the database server is able to determine, based on the selection criteria of the statement and the bounds of the partitions of the sales table, which partitions need not be accessed during execution of the statement. In the present example, the database server would be able to perform partition pruning that limits the execution plan of the statement to sal94Q2.
Similarly, database servers can perform partition pruning for queries with WHERE clauses that (1) specify equalities that involve the partition key (e.g. where saledate =94-02-05), (2) include IN lists that specify partition key values (e.g. where saledate IN (94-02-05, 94-03-06)), and (3) include IN subqueries that involve the partition key (e.g. where salesdate IN (select datevalue from T)).
In the preceding examples, partition pruning is performed on queries that contain relatively simple predicates (equality predicates, range-based predicates, IN list predicates). However, because partition pruning can significantly decrease the execution time of a query, it is desirable to provide techniques that enable database servers to perform partition pruning in situations where the predicates of the queries are more complex.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.